package com.example.linked;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照正序（数字最高位位于链表开始位置）的方式存储的,
 * 并且每个节点只能存储一位数字。
 * 将两个数相加，并以相同形式返回一个表示和的链表
 * 假设除了数字 0之外，这两个数都不会以0开头。
 */
public class AddNumByNormalOrderList {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(1);
        l2.next.next.next.next = new ListNode(7);

        ListNode res = addTwoNumbers(l1, l2);
        while (res != null) {
            System.out.print(res.val);
            res = res.next;
        }
    }

    /**
     * 解法一:
     * 1.遍历两个将两个链表转成数字字符串
     * 2.末尾对齐，逐位相加，逢十进一
     * 3.遍历两个字符串，从低位开始遍历相加，中短的位置补0
     *  ⼤大于2，则进位，将进位加到下上一位
     * 4.将结果字符串转成链表后返回
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode result = new ListNode(-1);
        // 1.遍历l1,l2得到两个数字字符串
        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();
        while (cur1 != null || cur2 != null) {
            if (cur1 != null) {
                sb1.append(cur1.val);
            }
            if (cur2 != null) {
                sb2.append(cur2.val);
            }

            cur1 = cur1 != null ? cur1.next : null;
            cur2 = cur2 != null ? cur2.next : null;
        }
//        System.out.println(sb1.toString());
//        System.out.println(sb2.toString());

        // 2.遍历两个字符串，从低位开始遍历相加，中短的位置补0,并将每位相加的结果头插法放入结果链表中
        int n = Math.max(sb1.length(), sb2.length()), carry = 0;
        // 从低位开始遍历相加，短的位置补0
        for (int i = 0; i < n; ++i) {
            int x = i < sb1.length() ? (sb1.charAt(sb1.length() - 1 - i) - '0') : 0;
            int y = i < sb2.length() ? (sb2.charAt(sb2.length() - 1 - i) - '0') : 0;
            int sum = x + y + carry;
            ListNode tmp = new ListNode(sum % 10);
            tmp.next = result.next;
            result.next = tmp;
            carry = sum / 10;
        }
        //进位有值，存入答案字符串中
        if (carry > 0) {
            ListNode tmp = new ListNode(1);
            tmp.next = result.next;
            result.next = tmp;
        }
        // 查看结果链表
        return result.next;
    }

    /**
     * 解法二:使用栈
     * 1.将两个链表的数字分别压入两个栈中
     * 2.依次取出来相加，存到结果链表中
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new LinkedList<Integer>();
        Deque<Integer> stack2 = new LinkedList<Integer>();
        // 把L1、L2中的数字依次压入栈中
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ans = null;
        //再依次取出来相加，存到节点中
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = ans;
            ans = curnode;
        }
        return ans;
    }
}
